package toOffer;

/**
 * <h3>toOffer</h3>
 *
 * @author YuanAo
 * @date 2024/6/17 10:03
 * @description <p>排序数组中只出现一次的数字</p>
 */

/**
 * 题目：在一个排序的数组中，除一个数字只出现一次之外，其他数字
 * 都出现了两次，请找出这个唯一只出现一次的数字。例如，在数组[1, 1, 2, 2,
 * 3, 4, 4, 5, 5]中，数字 3 只出现了一次
 */
public class toOffer11_2_70 {
    public static void main(String[] args) {
        int[] nums = {3, 3, 7, 7, 11, 11, 12};
        System.out.println(singleNonDuplicate(nums));
    }

    /**
     * 1,1 >> 0
     * 2,2 >> 1
     * 3,4 >> 2
     * 4,5 >> 3
     *
     * 2n+1个数，俩俩分组、分成n组，从第n>>1组开始比较：
     *（1）如果两个数字相同，那么那个只出现一次的数字一定在它的后面，因此接着查找它的后半部分。
     *（2.1）如果两个数字不相同，那么接着检查这一组是不是第1组。如果是第1组，那么这一组的第1个数字就是只出现一次的数字。
     *（2.2）如果不是第1组，那么第1组一定在它的前面，因此接着查找它的前半部分。
     * @param nums
     * @return
     */
    public static int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1 >> 1;
        while (left <= right){
            int mid = (left + right) >> 1;
            int i = mid << 1;
            if (i < nums.length - 1 && nums[i] != nums[i + 1]){
                if (mid == 0 || nums[i - 1] == nums[i - 2]){
                    return nums[i];
                }
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return nums[nums.length - 1];
    }

}